package example3;

//221.最大正方形

public class LeetCode221 {
    public static void main(String[] args) {
        int[][] arr = {{1, 0, 1, 0, 0},
                {1, 0, 1, 1, 1},
                {1, 1, 1, 1, 1},
                {1, 0, 0, 1, 0}};
        char[][] arr2 = {{'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0'}};
        char[][] arr3 = {{'1', '1'}, {'1', '1'}};
        System.out.println(new Solution221().maximalSquare(arr3));
    }
}

class Solution221 {
    //用一维dp优化空间复杂度
    //优化思路：
    //原来的思路是dp[i][j]二维数组表示以i,j这个元素为右下角的正方形的最大边长。
    //现在是改为dp[j]来存储以i,j这个元素为右下角的正方形的最大变长，
    //跟原来的一样，如果要想求i,j这个为右下角的正方形的最大变长，就必须要知道i-1,j-1和
    //i,j-1和i-1,j这三个下标dp的值，在原来二位数组的情况下，这3个值很好拿到，
    //但现在一维数组的情况下，就看下面的思路：
    //(1)i,j-1就是i,j左边的元素，对应的最大边长其实就是dp[j-1]，
    //因为dp[j-1]在dp[j]之前遍历，所以dp[j-1]在更新dp[j]之前已经更新了，
    //所以此时dp[j-1]记录的就是i,j-1左边的元素的最大边长。
    //(2)i-1,j是i,j上边的元素，其实就是dp[j]更新之前的dp[j]，因为循环的时候是两层循环，
    //外层循环是行，内层循环是列，所以当到i,j时，dp[j]还没有更新的情况下，存储的就是i-1,j的最大边长。
    //(3)接下来就是i-1,j-1，是i,j左上角的元素。这个的最大边长似乎拿不到，那我们就需要有个值prev
    //提前存储dp[i-1][j-1]，但是每次要怎么更新这个值呢，可以想象一下，在执行到当执行i,j时，
    //更新之前dp[j]其实就是i-1,j的值，那么当下次i,j执行完之后，此时的i-1,j就是下一次i,j+1
    //的左上角，那么只要在更新dp[j]之前，用temp临时存储dp[j]（实际是i-1,j的值），
    //然后dp[j]更新完之后，让prev = temp，这样就更新了prev的值，可以用于下次i,j+1的计算。

    //然后要注意处理好边界情况就行，特别是i = 0 和 j = 0的时候。
    public int maximalSquare(char[][] matrix) {
        int m = matrix[0].length;
        int[] dp = new int[m];
        int prev = 0;
        int max = 0;
        int temp = 0;
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<m;j++){
                if(j == 0){
                    prev = dp[j];
                    dp[j] = matrix[i][j] - 48;
                }else{
                    if(matrix[i][j] - 48 == 0){
                        dp[j] = 0;
                    }else{
                        temp = dp[j];
                        dp[j] = Math.min(Math.min(dp[j-1],dp[j]),prev) + 1;
                        prev = temp;
                    }
                }
                max = Math.max(max,dp[j]);
            }
        }
        return max * max;
    }

    //目前思路：
    //动态规划，dp[i][j]表示以以matrix[i][j]这个元素为右下角的正方形的最大变长，
    //最后找到dp[i][j]中最大的一个就行。
    //但重难点就在于如何求出所有的dp[i][j]，我想的就是，因为毕竟是动态规划，
    //所以dp[i][j]一定跟与它前面相邻的几个元素的只有关，也就是dp[i-1][j],dp[i][j-1],
    //dp[i-1][j-1]，经过验证发现，首先判断matrix[i][j]是否为1，如果为0，那么dp[i][j]=0;
    //如果为1，那么判断这3个值是否一样，如果一样，那么dp[i][j]就等于原有值+1;
    //如果不一样，那么dp[i][j]就等于3个中的最小值+1。
    public int maximalSquare2(char[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int[][] dp = new int[n][m];
        int max = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(i == 0 || j == 0){
                    dp[i][j] = matrix[i][j] - 48;
                }else{
                    if(matrix[i][j] - 48 == 0){
                        dp[i][j] = 0;
                    }else{
                        dp[i][j] = Math.min(Math.min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1]) + 1;
                    }
                }
                max = Math.max(max,dp[i][j]);
            }
        }
        return max * max;
    }
}
